package com.yanceysong.codetop.s31_s40;

import com.yanceysong.common.ListNode;


public class S36_Mid_142_环形链表_II {
    /**
     * 题目: 142. 环形链表 II (Linked List Cycle II)
     * LeetCode: <a href="https://leetcode.cn/problems/linked-list-cycle-ii/">...</a>
     * ----------------------------------------------------------------------
     * 描述:
     * 给定一个链表的头节点 head，若链表中存在环，则返回入环的第一个节点；否则返回 null。
     * 链表中如果某个节点可以通过连续跟踪 next 指针再次到达自身，则说明存在环。
     * 评测系统使用整数 pos 表示尾节点连接到的索引位置 (0-based)，-1 表示无环；pos 仅用于描述，不作为函数参数。
     * 要求: 不允许修改原链表结构；时间 O(n)，空间 O(1)。
     * ----------------------------------------------------------------------
     * 示例 1:
     * 输入: head = [3,2,0,-4], pos = 1  (尾部 -4 指向值为 2 的节点)
     * 输出: 1 (返回索引 1 的节点，即值 2)
     * 示意: 3 -> 2 -> 0 -> -4
     * .            ^              |
     * .            |______________|
     * .
     * 示例 2:
     * 输入: head = [1,2], pos = 0 (尾节点 2 指回头节点 1)
     * 输出: 0 (返回索引 0 的节点，值 1)
     * 示意: 1 -> 2
     * .      ^    |
     * .      |____|
     * <p>
     * 示例 3:
     * 输入: head = [1], pos = -1
     * 输出: null (无环)
     * ----------------------------------------------------------------------
     * 核心思路 (Floyd 判圈算法 + 数学证明):
     * 1. 使用快慢指针 (fast 每次 2 步, slow 每次 1 步)。
     * 2. 若无环: fast 或 fast.next 会先到达 null → 返回 null。
     * 3. 若相遇: slow 与 fast 在环内第一次相遇。
     * 4. 证明: 设
     * .    - 从 head 到入环点距离 = a (前缀长度)
     * .   - 入环点到首次相遇点距离 = b
     * .   - 相遇点到入环点剩余距离 = c (环长 = b + c)
     * .   运动方程: (slow 走的距离) = a + b; (fast 走的距离) = a + b + k*(b + c)
     * .   且 fast 速度是 slow 的 2 倍: 2(a + b) = a + b + k*(b + c)
     * .   → a + b = k*(b + c) = k*环长
     * .   → a = k*(b + c) - b = (k-1)*(b + c) + c
     * .   解释: 从相遇点再走 c 步就到入环点；而 head 走 a 步到入环点。
     * 5. 因此: 将一指针移回 head，两个指针同步每次走 1 步，再次相遇即入环点。
     * ----------------------------------------------------------------------
     * 步骤总结:
     * 1) 判空/边界: head 为空或只有一个节点直接返回 null。
     * 2) 第一阶段: 快慢指针查找相遇点；若无相遇返回 null。
     * 3) 第二阶段: 让一个指针回到 head，两指针同步前进，直到相遇 = 入环点。
     * 4) 返回该节点。
     * ----------------------------------------------------------------------
     * ASCII 动画示意 (示例 [A, B, C, D, E], D 为入环点, 环: D->E->F->G->D):
     * . head
     * .  A -> B -> C -> D -> E -> F -> G
     * .                ^                |
     * .                |________________|
     * . 第一阶段 (相遇示例位置 F):
     * .  slow:  A B C D E F
     * .  fast:  A C E G (绕回) E (再两步到 F) -> 相遇
     * . 第二阶段:
     * .  ptr1 从 head(A) 走: A B C D
     * .  ptr2 从 F      走: F G D  -> 相遇 D = 入环点
     * ----------------------------------------------------------------------
     * 复杂度:
     * - 时间: O(n)  每个指针最多遍历 O(n) 节点。
     * - 空间: O(1)  仅使用常数指针变量。
     * ----------------------------------------------------------------------
     * 关键洞察 / 易错点:
     * 1. 相遇后不能直接返回 slow (那是环内某点, 非必然入口)。
     * 2. 必须将一指针移回 head 再同步前进。
     * 3. 若用 HashSet 记录访问过的节点也可解, 但空间 O(n) 不满足进阶要求。
     * 4. do-while 写法要保证第一次循环前不解引用 null；这里采用更直观的 while 判空写法。
     * 5. 只有 fast 与 slow 相等后才进入第二阶段；否则直接无环返回。
     * ----------------------------------------------------------------------
     * 拓展: 如何求环长度? 在第一次相遇点固定一指针, 另一指针继续一圈计数即得环长。
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        // 第一阶段: 快慢指针寻找是否有环 (Floyd 判圈)
        ListNode slowPointer = head;           // 每次走一步
        ListNode fastPointer = head;           // 每次走两步

        while (fastPointer != null && fastPointer.next != null) {

            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;

            if (slowPointer == fastPointer) { // 找到第一次相遇 (在环内)
                // 第二阶段: 一个指针回到头部, 同步前进直到再次相遇
                ListNode indexFromHead = head;
                ListNode indexFromMeet = slowPointer; // 或 fastPointer

                while (indexFromHead != indexFromMeet) {
                    indexFromHead = indexFromHead.next;
                    indexFromMeet = indexFromMeet.next;
                }

                return indexFromHead; // 或 indexFromMeet
            }
        }
        return null; // 无环
    }

    /**
     * 计算环的长度: 给定环入口节点 entry (须保证非空且确为环入口)，沿 next 指针遍历直到回到入口。
     * 若 entry 为 null（无环），返回 0。
     * 时间 O(Lc) 其中 Lc 为环长；空间 O(1)。
     */
    public int cycleLength(ListNode entry) {
        if (entry == null) return 0; // 无环
        int len = 1;
        ListNode cur = entry.next;
        while (cur != entry) { // 首次回到入口即完成一圈
            len++;
            cur = cur.next;
        }
        return len;
    }

    // ============================ 辅助测试方法 ============================

    /**
     * 构造带环链表
     *
     * @param values 节点顺序值
     * @param pos    尾节点指向的索引 (0-based), -1 表示无环
     * @return 头节点
     */
    private static ListNode buildCyclicList(int[] values, int pos) {
        if (values == null || values.length == 0) return null;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        ListNode cycleEntry = null;
        for (int i = 0; i < values.length; i++) {
            cur.next = new ListNode(values[i]);
            cur = cur.next;
            if (i == pos) cycleEntry = cur;
        }
        if (pos != -1) {
            cur.next = cycleEntry; // 创建环
        }
        return dummy.next;
    }

    /**
     * 根据 head 和 期望入口节点引用(或 null) 验证 detectCycle 结果。
     */
    private static void assertCycle(S36_Mid_142_环形链表_II solver, ListNode head, ListNode expectedEntry, String caseName) {
        ListNode result = solver.detectCycle(head);
        if (result != expectedEntry) {
            System.out.println("[失败] " + caseName + " -> 期望: " + (expectedEntry == null ? "null" : String.valueOf(expectedEntry.val))
                    + ", 实际: " + (result == null ? "null" : String.valueOf(result.val)));
            assert false : caseName + " 未通过";
        } else {
            System.out.println("[通过] " + caseName + " -> 入口: " + (result == null ? "null" : result.val));
        }
    }

    public static void main(String[] args) {
        S36_Mid_142_环形链表_II solver = new S36_Mid_142_环形链表_II();
        System.out.println("=== 环形链表 II 测试开始 ===\n");

        // 1. 空链表
        assertCycle(solver, null, null, "用例1: 空链表");
        assert solver.cycleLength(null) == 0;

        // 2. 单节点无环
        ListNode single = new ListNode(1);
        assertCycle(solver, single, null, "用例2: 单节点无环");
        assert solver.cycleLength(null) == 0;

        // 3. 单节点自环 (环长 = 1)
        ListNode singleCycle = new ListNode(7);
        singleCycle.next = singleCycle;
        assertCycle(solver, singleCycle, singleCycle, "用例3: 单节点自环");
        assert solver.cycleLength(singleCycle) == 1 : "环长度应为1";

        // 4. 多节点无环
        ListNode noCycle = buildCyclicList(new int[]{1, 2, 3, 4, 5}, -1);
        assertCycle(solver, noCycle, null, "用例4: 多节点无环");
        assert solver.cycleLength(null) == 0;

        // 5. 入环点为头节点 (环: 10->20->30->10, 长度=3)
        ListNode headCycle = buildCyclicList(new int[]{10, 20, 30}, 0); // 尾部指回 index 0
        assertCycle(solver, headCycle, headCycle, "用例5: 入环点为头");
        assert solver.cycleLength(headCycle) == 3 : "环长度应为3";

        // 6. 入环点在中间 (示例: [3,2,0,-4], pos=1)  环: 2->0->-4->2  长度=3
        ListNode midCycle = buildCyclicList(new int[]{3, 2, 0, -4}, 1);
        ListNode midEntry = midCycle.next; // index 1 值2
        assertCycle(solver, midCycle, midEntry, "用例6: 中间入环");
        assert solver.cycleLength(midEntry) == 3 : "环长度应为3";

        // 7. 较长链表，尾部指向中间 (pos=4)  环: 5->6->7->8->5  长度=4
        ListNode longCycle = buildCyclicList(new int[]{1, 2, 3, 4, 5, 6, 7, 8}, 4);
        ListNode longEntry = longCycle;
        for (int i = 0; i < 4; i++) longEntry = longEntry.next; // index 4 值5
        assertCycle(solver, longCycle, longEntry, "用例7: 较长链表中部入环");
        assert solver.cycleLength(longEntry) == 4 : "环长度应为4";

        // 8. 环长度为1 (尾指向最后一个节点自身) => pos=2, 环: 节点值9  长度=1
        ListNode selfTailCycle = buildCyclicList(new int[]{9, 9, 9}, 2);
        ListNode tailEntry = selfTailCycle;
        for (int i = 0; i < 2; i++) tailEntry = tailEntry.next; // index 2
        assertCycle(solver, selfTailCycle, tailEntry, "用例8: 尾节点自环");
        assert solver.cycleLength(tailEntry) == 1 : "环长度应为1";

        // 9. 环长度为2  (pos=2, 环: 7->8->7  长度=2)
        ListNode cycle2 = buildCyclicList(new int[]{5, 6, 7, 8}, 2);
        ListNode entry2 = cycle2;
        for (int i = 0; i < 2; i++) entry2 = entry2.next; // index 2 值7
        assertCycle(solver, cycle2, entry2, "用例9: 环长度为2");
        assert solver.cycleLength(entry2) == 2 : "环长度应为2";

        System.out.println("\n=== 所有测试用例通过 (含环长度校验) ===");
    }
}
